
//53.最大子数组和
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //连续子数组的和
        //当遍历到第i个位置的时候,在前面找最小前缀和,将i位置的前缀和-最小前缀和就可以得到[0,i]位置中最大子数组
        int n = nums.size(),prev = 0 ,ret=INT_MIN;
        vector<int> lsum(n+1);
        for(int i = 0; i < n;i++)
        {
            lsum[i+1] = lsum[i] + nums[i];      //存储前缀和最大值
            ret = max(ret,lsum[i+1]-prev);      //更新答案
            prev = min(prev,lsum[i+1]);         //更新前缀和最小值
        }
        return ret;
    }
};